package fun.ticsmyc.graph;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 最小生成树 ： Kruskal算法
 * leetcode 1584 连接所有点的最小费用
 * @author Ticsmyc
 * @package fun.ticsmyc.graph
 * @date 2021-01-30 16:04
 */
public class Kruskal {

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        UnionFind unionFind = new UnionFind(n);

        PriorityQueue<Edge> edges = new PriorityQueue<>((a, b)->a.len-b.len);
        for(int i=0;i<n;++i){
            for(int j = i+1; j<n;++j){
                edges.add(new Edge(dist(points,i,j),i,j));
            }
        }

        int ans = 0;
        int num = 0;
        while(!edges.isEmpty()){
            Edge edge = edges.poll();
            int len = edge.len;
            int x =edge.x;
            int y =edge.y;
            if(unionFind.unionSet(x,y)){
                ans += len;
                num++;
                if(num ==n){
                    break;
                }
            }
        }
        return ans;
    }

    public int dist(int[][] points, int x, int y){
        return Math.abs(points[x][0]-points[y][0]) + Math.abs(points[x][1]- points[y][1]);
    }

    private class UnionFind{
        int[] f;
        int[] rank;
        int n;

        public UnionFind(int n) {
            this.n = n;
            this.rank = new int[n];
            Arrays.fill(rank,1);
            this.f = new int[n];
            for(int i=0;i<n;++i){
                this.f[i]=i;
            }
        }
        public int find(int x){
            if(f[x] ==x) return x;
            return f[x] = find(f[x]);
        }
        public boolean unionSet(int x, int y){
            int fx = find(x);
            int fy =find(y);
            if(fx ==fy){
                return false;
            }
            if(rank[fx] < rank[fy]){
                int tmp = fx;
                fx =fy;
                fy = tmp;
            }
            rank[fx] += rank[fy];
            f[fy]=f[fx];
            return true;
        }
    }

    private class Edge{
        int len;
        int x;
        int y;
        public Edge(int len, int x, int y) {
            this.len = len;
            this.x = x;
            this.y = y;
        }
    }
}
